#include <stdio.h>

int singleNonDuplicate(int* nums, int numsSize);

int main(){
	int nums[] = {1,1,2};
	int result = singleNonDuplicate(nums, sizeof(nums)/sizeof(int));
	printf("the result is %d", result);
	return 0;
}

int singleNonDuplicate(int* nums, int numsSize) {
    int startIdx = 0;
	int endIdx = numsSize-1;
	int mid = (endIdx+startIdx)/2;
	while(endIdx - startIdx > 2){
		int remainOdd = (endIdx - startIdx)/2 % 2 ? 1 : 0;
		if(nums[mid] == nums[mid-1])
			if(remainOdd)
				startIdx = mid+1;
			else
				endIdx = mid;
		else if(nums[mid] == nums[mid+1])
			if(remainOdd)
				endIdx = mid-1;
			else
				startIdx = mid;
		else
			return nums[mid];
		mid = (endIdx+startIdx)/2;
	}
	if(nums[mid] == nums[mid-1])
		return nums[mid+1];
	return nums[mid-1];
}
